#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        if (word1.size() < word2.size())
            swap(word1, word2);
        int size = word2.size()+1;
        int* dp1 = new int[size];
        int* dp2 = new int[size];
        memset(dp1, 0, size * sizeof(int));
        for (int i = 0; i < word1.size()+1; ++i) {
            for (int j = 0; j < word2.size()+1; ++j) {
                if (i == 0 || j == 0)
                    dp2[j] = i + j;
                else if (word1[i - 1] == word2[j - 1])
                    dp2[j] = dp1[j - 1];
                else {
                    dp2[j] = 1 + min(dp2[j - 1], dp1[j]);
                }
            }
            swap(dp1, dp2);
        }
        return dp1[size - 1];
    }
};